# -*- coding: utf-8 -*-

class QuickSort:
        '''
        Classe do algoritmo QuickSort
        '''
        def __init__(self, A):
                '''
                Construtor da classe.

                Parametros de entrada:
                    A - Lista com elementos a ordenar
                '''
                self.A = A
                self.sort(0, len(self.A) - 1)

        def sort(self, p, r):
                """
                        Método para ordenar as partições (divisao da lista) criadas a partir da lista
                Parâmetros: 
                        A - Lista com elementos por ordenar
                        p - Posição inicial da tabela[0]
                        r - Posição final da tabela
                """
                if p < r:
                        q = self.partition(p, r)
                        self.sort(p, q - 1)
                        self.sort(q + 1, r)

        def partition(self, p, r):
                """
                        Método que cria a divisão da lista por ordenar em duas sublistas.
                """
                x = self.A[r]
                i = p - 1
                for k in range(p, r):
                        if self.A[k] <= x:
                                i += 1
                                self.A[i], self.A[k] = self.A[k], self.A[i]
                self.A[i + 1], self.A[r] = self.A[r], self.A[i + 1]
                return (i + 1)
